The present application relates to the processing of lightweight directory access protocol (LDAP) searches.
The Lightweight Directory Access Protocol (LDAP) is a network protocol for accessing directories. It is based on the X.500, a Comité Consultatif International Téléphonique et Télégraphique (CCITT) standard for directory services that is part of the Open Systems Interconnection (OSI) suite of services. The X.500 directory service is a global directory service. Its components cooperate to manage information about objects such as countries, organizations, people, machines, and so on in a worldwide scope. It provides the capability to look up information by name (a “white pages” service) and to browse and search for information (a “yellow pages” service).
The information is held in a directory information base (DIB). Entries in the DIB are arranged in a tree structure called the directory information tree (DIT). Each entry is a named object and consists of a set of attributes. Each attribute has a defined attribute type and one or more values. The directory schema defines the mandatory and optional attributes for each class of object (called the object class). Each named object may have one or more object classes associated with it.
The X.500 namespace is hierarchical. An entry is unambiguously identified by a distinguished name (DN). A distinguished name is the concatenation of selected attributes from each entry, called the relative distinguished name (RDN), in the tree along a path leading from the root down to the named entry. Users of the X.500 directory may (subject to access control) interrogate and modify the entries and attributes in the DIB.
Although the concepts of distinguished names and relative distinguished names are core to the X.500 model, the X.500 standard itself does not define any string representation for names. What is communicated between the X.500 components is the structural form of names. The reasoning behind this is that the standard is sufficient to allow different implementations to interoperate. String names are not communicated between different implementations. Instead, they are necessary only for interaction with end-users. For that purpose, the standard allows any representation, not necessarily only string representations.
Each system that is based on the X.500 model, such as the LDAP, defines its own string representation. For example, in the LDAP, a DN's RDNs are arranged right to left, separated by the comma character (“,”). For example, a name that starts with “c=us” at the top and leads to “cn=Rosanna Lee” at the leaf may be expressed in the string:
cn=Rosanna Lee, ou=People, o=Sun, c=us
Internet Engineering Task Force (IETF) Request For Comments (RFC) 1777 defines what is now called version 2 of the LDAP (or LDAP v2). LDAP v2 is a protocol that can be easily implemented, with special focus on being able to build small and simple clients. One way that LDAP v2 achieves simplification is by using a lot of strings and minimizing wherever possible the use of structures. DNs, for example, are represented in the protocol as strings, as are attribute type names and many attribute values. The protocol consists of the client's sending requests to the server, to which the server responds, though not necessarily in the same order in which the requests were sent. Each request is tagged with an ID so that requests and responses can be matched. The protocol works over either Transmission Control Protocol (TCP) or User Datagram Protocol (UDP), although the TCP version is most commonly used. Because of the focus on clients, the LDAP community also defines standards for the string representation of DNs (in IETF RFC 1779), search filters (in IETF RFC 1960), and attribute syntaxes (in IETF RFC 1778), for a C language-based application programming interface (API) (in IETF RFC 1823), and for the format of uniform resource locators (URLs) for accessing LDAP services (in IETF RFC 1959). IETF RFCs 1777, 1779, 1960, 1778, 1823, and 1959, available online at ietf.org, are incorporated by reference herein.
Various operations are defined in the LDAP v2. The “bind” operation is used to start a connection with the LDAP server. The LDAP is a connection-oriented protocol. The client specifies the protocol version and the client authentication information. The “unbind” operation is used to terminate the connection with the LDAP server. The “search” operation is used to search the directory. The client specifies the starting point (base object) of the search, the search scope (the object only, its children, or the subtree rooted at the object), and a search filter (as discussed in IETF RFC 1960). It can also supply other information to control the search, such as the names of the attributes to return and the size and time limits. The search results consist of LDAP entries (and the attributes requested) that satisfy the filter. The “modify” operation is used to modify an existing entry. The client specifies the name of the entry to be modified and a list of modifications. Each modification consists of an attribute and information regarding whether its values are to be added, deleted, or replaced. The “add” operation is used to add a new entry. The client specifies the name of the new entry and a set of attributes for the new entry. The “delete” operation is used to remove an existing entry. The client specifies the name of the entry to remove. The “modify RDN” operation is used to change the RDN of the last component of an existing entry (that is, to assign the entry a new name in the same context). The client specifies the DN for the entry and the new RDN. The “compare” operation is used to test whether an entry has an attribute/value pair. The client specifies the name of the entry and the name and value to check. The “abandon” operation is used to terminate an outstanding request. IETF RFC 1960, available online at ietf.org, is incorporated by reference herein.
One of the most useful features that an LDAP directory offers is its “yellow pages,” or “search,” service, mentioned above in the discussion of operations. An application can compose a query consisting of attributes of entries that the application is seeking and submit that query to the directory. The directory then returns a list of entries that satisfy the query. For example, an application could ask the directory for all entries with a bowling average greater than 200 or all entries that represent a person with a surname beginning with “Sch.” The simplest form of search requires that the application specify a set of attributes that an entry must have and the name of the target context in which to perform the search. In addition to specifying a search using a set of attributes, an application can specify a search in the form of a search filter. A search filter is a search query expressed in the form of a logical expression. The syntax of search filters is described in IETF RFC 2254. The following search filter specifies that the qualifying entries must have an “sn” attribute with a value of “Geisel” and a “mail” attribute with any value:
(&(sn=Geisel)(mail=*))
Each item in the filter is composed using an attribute identifier and either an attribute value or symbols denoting the attribute value. For example, the item “sn=Geisel” means that the “sn” attribute must have the attribute value “Geisel” and the item “mail=*” indicates that the “mail” attribute must be present. Each item is enclosed within a set of parentheses, as in “(sn=Geisel).” These items are composed using logical operators such as “&” (conjunction) to create logical expressions, as in the immediately foregoing example. Each logical expression can be further composed of other items that themselves are logical expressions, as in the following search filter:
(|(& (sn=Geisel) (mail=*)) (sn=L*))
This example requests either entries that have both a “sn” attribute of “Geisel” and the “mail” attribute or entries whose “sn” attribute begins with the letter “L.” IETF RFC 2254, available online at ietf.org, is incorporated by reference herein.
The LDAP v3 (defined in RFC 2251) is designed to address some of the limitations of the LDAP v2 in the areas of internationalization, authentication, referral, and deployment. It also allows new features to be added to the protocol without also requiring changes to the protocol. This is done by using extensions and controls. In addition to the repertoire of predefined operations, such as “search” and “modify,” the LDAP v3 defines an “extended” operation. The “extended” operation takes a request as an argument and returns a response. The request contains an identifier that identifies the request and the arguments of the request. The response contains the results of performing the request. The pair of “extended” operation request/response is called an extension. For example, there can be an extension for “Start TLS,” which is a request for the client to the server to activate the Start TLS protocol. These extensions can be standard (defined by the LDAP community) or proprietary (defined by a particular directory vendor). Another way to add new features is by using a control. The LDAP v3 allows the behavior of any operation to be modified through the use of controls. Any number of controls may be sent along with an operation, and any number of controls may be returned with its results. For example, a “sort” control can be sent along with a “search” operation, where the “sort” control can tell the LDAP server to sort the results of the search according to a “name” attribute. Like extensions, such controls can be standard or proprietary. IETF RFC 2251, available online at ietf org, is incorporated by reference herein.
In the LDAP v3, a control can be either a request control or a response control. A request control is sent from the client to the server along with an LDAP operation. A response control is sent from the server to the client along with an LDAP response. An application typically does not deal directly with the control interface. Instead, it deals with classes that implement this interface. The application gets control classes either as part of a repertoire of controls standardized through the IETF or from directory vendors (vendor-specific controls). The request control classes can have constructors that accept arguments in a type-safe and user-friendly manner, and the response control classes can have access methods for getting the data of the response in a type-safe and user-friendly manner.
When a client sends a request control to a server, it specifies the control's criticality. The criticality determines whether the server can ignore the request control. When the server receives a critical request control, the server either processes the request with the control or rejects the entire request. When a server receives a noncritical request control, the server processes the request either with the control or by ignoring the control. The server does not reject the request simply because the server does not support the control. Additionally, a designer defining a control assigns that control a unique object identifier (OID). For example, the “sort” control has an identifier of 1.2.840.113556.1.4.473.
Although the LDAP provides an operation for searching a directory for entries whose attributes have specified values, using the search operation can be quite unwieldy when the performance of certain kinds of tasks is desired. One kind of task to which the search operation is not particularly well suited is a search for entities that are formally related to each other in a manner that is not captured by the hierarchical structure of the directory itself. For example, although each person's entry in a business organization's directory might indicate attributes that identify the entries of the person's friends, the hierarchical structure of the directory is not likely to be constructed based on friendships, and so there is not necessarily an easy way of determining a specified person's extended network of friends using the search operation. As matters currently stand, if a particular entry indicated that a particular person has three friends, then an application would issue a first search operation to the LDAP server to obtain the particular entry from the LDAP server, and then the application would inspect the “friends” attributes of that particular entry to determine who the particular person's immediate friends are. Next, to find the friends of those people (as part of an overarching attempt to discover the particular person's extended friends network), the application would issue subsequent separate search operations to the LDAP server for each immediate friend to obtain that immediate friend's entry from the LDAP server, and then the application would inspect the “friends” attributes of each of those entries to determine who the friends of the particular person's immediate friends are.
As can be imagined, the multiplicity of LDAP search operations complicates the design of a client application that performs such tasks relative to an LDAP directory. The multiplicity of LDAP search operations additionally degrades the performance of the overarching search task due to the consumption of a significant quantity of processing cycles on machines executing the client application and the LDAP server. The multiplicity of LDAP search operations also increases the expense of the overarching search task in terms of networking resources due to the significant network bandwidth that is consumed by each request-response exchange between the client application and the LDAP server.